package com.zdp.leetcodeMiddle;


import com.zdp.util.ListNode;

import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。
* 它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
* */
public class 两数相加II_445 {

    /*
     * 这个我不是做过嘛  见题目 ： 链表求和_02_05
     * 正序添加 ： 利用数组暂存结果 然后处理进位
     * */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> list = new ArrayList<>();
        list.add(0); // 存放首位的进位
        ListNode p1 = l1;
        ListNode p2 = l2;
        // 处理长短不一的情况
        while(p1!=null && p2!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        if(p1 == null){ // l1 比较短
            p1 = l2;
            while(p2 != null){
                p2 = p2.next;
                list.add(p1.val);
                p1 = p1.next;
            }
            p2 = p1;
            p1 = l1;
        }else if(p2 == null){
            // l2 比较短
            p2 = l1;
            while(p1 != null){
                p1 = p1.next;
                list.add(p2.val);
                p2 = p2.next;
            }
            p1 = p2;
            p2 = l2;
        }
        // 长短不一情况处理完毕 ，开始添加
        while(p1!=null && p2 !=null){
            list.add(p1.val + p2.val);
            p1 = p1.next;
            p2 = p2.next;
        }
        // 处理
        ListNode head = new ListNode();
        ListNode tail = head;
        for(int i=list.size()-1; i >0 ; i--){
            // 处理一下进位吧
            list.set(i-1,list.get(i-1) + list.get(i)/10);
            list.set(i,list.get(i)%10);
        }
        // 处理前缀0
        int j =0;
        while(list.get(j) ==0 && j < list.size()-1){
            j++;
        }
        for(int i=j;i<list.size() ; i++){
            // 填充到链表
            ListNode  tt = new ListNode(list.get(i));
            tt.next = tail.next;
            tail.next = tt;
            tail = tt;
        }
        return head.next;

    }
}
